๐Ÿ‘ฉโ€๐Ÿ’ป 86053. ๊ธˆ๊ณผ ์€ ์šด๋ฐ˜ํ•˜๊ธฐ

@Seongukbaek Posted July 30, 2022 ยท Updated July 30, 2022 ยท 3 min read

๋ฌธ์ œ

Programmers - ๊ธˆ๊ณผ ์€ ์šด๋ฐ˜ํ•˜๊ธฐ

๐Ÿ“ Logic

for (i = 0; i < n; i++) { // ์ดˆ๊ธฐํ™” gCur = g[i]; sCur = s[i]; wCur = w[i]; tCur = t[i]; gsCur = gCur + sCur; // ์™•๋ณต ํšŸ์ˆ˜ roundCnt = (long) Math.ceil((double) (T / tCur) / 2); // ์ด ๊ด‘๋ฌผ ๋ฌด๊ฒŒ = ์™•๋ณต ํšŸ์ˆ˜ * ํ•œ ๋ฒˆ์— ์šด๋ฐ˜ ๊ฐ€๋Šฅํ•œ ๊ด‘๋ฌผ ๋ฌด๊ฒŒ wAll = roundCnt * wCur; // ๊ฐ ๋„์‹œ์—์„œ ์šด๋ฐ˜ํ•œ ๊ธˆ์˜ ๋ฌด๊ฒŒ gMax += Math.min(gCur, wAll); // ๊ฐ ๋„์‹œ์—์„œ ์šด๋ฐ˜ํ•œ ์€์˜ ๋ฌด๊ฒŒ sMax += Math.min(sCur, wAll); // ๊ฐ ๋„์‹œ์—์„œ ์šด๋ฐ˜ํ•œ ๊ธˆ๊ณผ ์€์˜ ๋ฌด๊ฒŒ gsMax += Math.min(gsCur, wAll); }
  • ์šด๋ฐ˜ ๊ฐ€๋Šฅํ•œ ๊ธˆ, ์€, ๊ธˆ๊ณผ ์€์˜ ์ด ๋ฌด๊ฒŒ๋ฅผ ๊ณ„์‚ฐํ•œ๋‹ค.
if (a <= gMax && b <= sMax && ab <= gsMax) { right = T - 1; answer = T; } else left = T + 1;
  • ์šด๋ฐ˜ ๊ฐ€๋Šฅํ•œ ๊ธˆ, ์€, ๊ธˆ๊ณผ ์€์˜ ์–‘์„ ํ†ตํ•ด ๊ด‘๋ฌผ์„ ๋ชจ๋‘ ์˜ฎ๊ธธ ์ˆ˜ ์žˆ๋Š”์ง€ ํŒ๋‹จํ•œ๋‹ค.
  • ์ฃผ์–ด์ง„ ์‹œ๊ฐ„ ๋‚ด์— ๊ธˆ๊ณผ ์€์— ๋Œ€ํ•ด์„œ๋Š” ์šด๋ฐ˜ํ•œ๋‹คํ•ด๋„, ์ด ํ•„์š”ํ•œ ๊ด‘๋ฌผ ์–‘์„ ๋งŒ์กฑํ•˜์ง€ ๋ชปํ•˜๋Š” ๊ฒฝ์šฐ๋Š” ์šด๋ฐ˜ํ•  ์ˆ˜ ์—†์œผ๋ฏ€๋กœ, ์ด์— ๋Œ€ํ•œ ํ™•์ธ์ด ํ•„์š”ํ•˜๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
class Solution { public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) { long max = (long) (1e9 * 2 * 1e5 * 2); long left = 0, right = max, T; int n = g.length, i; long answer = max; long gMax, sMax, gsMax; long gCur, sCur, wCur, tCur, gsCur; long roundCnt, wAll, ab = a + b; while (left <= right) { T = (left + right) / 2; gMax = sMax = gsMax = 0; for (i = 0; i < n; i++) { // ์ดˆ๊ธฐํ™” gCur = g[i]; sCur = s[i]; wCur = w[i]; tCur = t[i]; gsCur = gCur + sCur; // ์™•๋ณต ํšŸ์ˆ˜ roundCnt = (long) Math.ceil((double) (T / tCur) / 2); // ์ด ๊ด‘๋ฌผ ๋ฌด๊ฒŒ = ์™•๋ณต ํšŸ์ˆ˜ * ํ•œ ๋ฒˆ์— ์šด๋ฐ˜ ๊ฐ€๋Šฅํ•œ ๊ด‘๋ฌผ ๋ฌด๊ฒŒ wAll = roundCnt * wCur; // ๊ฐ ๋„์‹œ์—์„œ ์šด๋ฐ˜ํ•œ ๊ธˆ์˜ ๋ฌด๊ฒŒ gMax += Math.min(gCur, wAll); // ๊ฐ ๋„์‹œ์—์„œ ์šด๋ฐ˜ํ•œ ์€์˜ ๋ฌด๊ฒŒ sMax += Math.min(sCur, wAll); // ๊ฐ ๋„์‹œ์—์„œ ์šด๋ฐ˜ํ•œ ๊ธˆ๊ณผ ์€์˜ ๋ฌด๊ฒŒ gsMax += Math.min(gsCur, wAll); } // ์šด๋ฐ˜์ด ๊ฐ€๋Šฅํ•œ ๊ฒฝ์šฐ, ๋” ์งง์€ ์‹œ๊ฐ„์„ ํƒ์ƒ‰ if (a <= gMax && b <= sMax && ab <= gsMax) { right = T - 1; answer = T; } else left = T + 1; } return answer; } }

โœ๏ธ Review

  • ์ง„์งœ ๋ช‡๋ฒˆ์„ ๋ด๋„ ํ’€์ด๊ฐ€ ์–ด๋ ต๋‹ค. ์ž˜ ์ดํ•ด๊ฐ€ ์•ˆ๋œ๋‹ค ...
@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€